package oj;

//二叉树的最近公共祖先：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
//百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
public class Solution_236 {
    public static boolean containsNode(TreeNode root, TreeNode targetNode){
        if(root == null){
            return false;
        }
        if(root == targetNode){
            return true;
        }
        return containsNode(root.left,targetNode) || containsNode(root.right,targetNode);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //p 和 q在 root 树中:p 和 q 的分布情况有四种：是根结点，都在左子树内，都在右子树内，在不同的子树内
        //断言 root != null
        if(root == p || root == q){
            return root;
        }
        boolean pInLeft = containsNode(root.left,p);
        boolean qInLeft = containsNode(root.left,q);
        if(pInLeft == true && qInLeft == true){
            //说明都在左子树内，对左子树进行递归
            //注意这里不能直接返回root.left,因为虽然 p 和 q 都在左子树内，但是可能在左子树的子树内，所以要进行递归
            return lowestCommonAncestor(root.left,p,q);
        }
        if(pInLeft == false && qInLeft == false){
            //同理都在右子树内，对右子树进行递归
            return lowestCommonAncestor(root.right,p,q);
        }
        //不是上面的情况，则说明两个结点在不同的子树中，这时没有必要进行递归，最近的公共祖先结点就是根结点
        return root;
    }
}
